(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "mit :: lcs :: tm :: MIT-LCS-TM-035"

B 



BIBLIOGRAPHIC DATA 
SHEET 



1. Report No. 

MAC TM-35 



3. Recipient's Accession No. 



4. Title and Subtitle 

An Interactive Implementation of the Todd-Coxeter Algorithm 



5. Report Date . Issued 

December 1973 



7. Author(s) 

Richard J, Bonneau 



8- Performing Organization Rept. 

MAC TM-3.5 



9. Performing Organization Name and Address 

PROJECT MAC; MASSACHUSETTS INSTITUTE OF TECHNOLOGY : 
545 Technology Square, Cambridge, Massachusetts 0213 9 



10. Project/Task/Work Unit No. 



11. Contract/Grant No. 



N00014-70-A-0362-0006 



12. Sponsoring Organization Name and Address 

Office of Naval Research 
Department of the Navy 
Information Systems Program 
Arlington. Va 22217 



13. Type of Report & Period 

Covered: Interim 
Scientific Report 



14. 



15. Supplementary Notes 



16. Abstracts 

The Todd-Coxeter algorithm provides a systematic approach to the 
enumeration of cosets of a finitely presented group. This memo describes 
an interactive implementation of algorithm, including a manual on its use, 
examples, and methods of accessing the program. Applications of this 
algorithm are also discussed. 



17. Key Words and Document Analysis. 17a. Descriptors 

Group Theory 
Symbol Manipulation 



17b. Identifiers/Open-Ended Terms 



17c COSATI Field/Group 



18. Availability Statement 

Unlimited Distribution 

Write Project MAC Publications 



19. Security Class (This 
Report) 

UNCLASSIFIED 



20. Security Class (This 
Page 

UNCLASSIFIED 



21. No. of Pages 
26 



22. Price 



FORM NT1S-35 (REV, 3-72) 



THIS FORM MAY BE REPRODUCED 



USCOMM-DC ^ 4 952- P 72 



INSTRUCTIONS FOR COMPLETING FORM NTIS-35 (10-70) (Bibliographic Data Sheet based on COSATI 
Guidelines to Format Standards for Scientific and Technical Reports Prepared by or for the Federal Government, 
PB-180 600). 

1. Report Number. Each individually bound report shall carry a unique alphanumeric designation selected by the performing 
organization or provided by the sponsoring organization. Use uppercase letters and Arabic numerals only. Examples 
FASEB-NS-87 and FAA-RD-68-09. 



2. Leave blank. 

3. Recipient's Accession Number. Reserved for use by each report recipient. 



/ 



4. Title and Subtitle. Title should indicate clearly and briefly the subject coverage of the report, and be displayed promi- 
nently. Set subtitle^ if used, in smaller type or otherwise subordinate it to orain title. When a report is prepared in more 
than one volume, repeat the primary title, add volume number and include suDtitle for the specific volume. 

5- Report Date. Fach report sKall carry a date indicating at least month anVyear. Indicate the basis on which it was selected 
(e.g., date of issue, date of approval, date of preparation. 

6. Performing Organization Code. Le^ye blank. 

7. Author(s). Give name(s) in conventional order (e.g., John R.^oe, or J.Robert Doe). List author's affiliation if it differs 
from the performing organization. \ 

8- Performing Organization Report Number. Insert if performyfg organization wishes to assign this number. 

9- Performing Organization Name and Address. Giv\namtff street, city, state, and zip code. List no more than two levels of 
an organizational hierarchy. Display the name of t^eyfcrganizat ion exactly as it should appear in Government indexes such 
as USGRDR-I. 



10. Project/Task/Work Unit Number. Use the projecyf task a^ntd work unit numbers under which the report was prepared. 

/ \ 

11. Contract/Grant Number. Insert contract or grajft number unde^ which report was prepared. 



12. Sponsoring Agency Name and Address. Inclride zip code 



\ 



\ 



13. Type of Report and Period Covered. Indicate interim, final, etc., aV , if applicable, dates covered 



\ 



14. Sponsoring Agency Code. Leave blank. 



\ 



15. Supplementary Notes. Enter information not included elsewhere but useful, such as: Prepared in cooperation with . . . 
Translation of . . . Presented at conference of . . . To be published in . . .\ Supersedes . . . Supplements . . . 

16. Abstract. Include a brief (200 words or less) factual summary of the most significant information contained in the report. 
If the report contains a significant bibliography or literature survey, mention it hefce- 

17. Key Words and Document Analysis, (a). Descriptors. Select from the Thesaurus of h.ngineering and Scientific Terms the 
proper authorized terms that identify the major concept of the research and are sufficiently specific and precise to be used 
as index entries for cataloging. \ 

(b). Identifiers and Open-Ended Terms. Use identifiers for project names, code names, equipment designators, etc. Use 
open-ended terms written in descriptor form for those subjects for which no descriptor exists. 

(c). COSATI Field/Group. Field and Group assignments are to be taken from the 1965 COSATI Subject Category List. 
Since the majority of documents are mukidisciplinary in nature, the primary Field/Group assignment(s) will be the specific 
discipline, area of human endeavor, or type of physical object. The application(s) will be cross-referenced with secondary 
Field/Group assignments that will follow the primary posting(s). 

18. Distribution Stotement. Denote releasability to the public or limitat ion for reasons other than security for example "Re- 
lease unlimited**. Cite any availability to the public, with address and price. 

19 & 20. Security Classification. Do not submit classified reports to the National Technical 

21. Number of Pages. Insert the total number of pages, including this one and unnumbered pages, but excluding distribution 
list, if any. 

22. Price. Insert the price set by the National Technical Information Service or the Government Printing Office, if known. 



FORM NTIS-35 (REV 3-72) 



USCOMM-DC 14952-P72 



MAC TECHNICAL MEMORANDUM 35 



AN INTERACTIVE IMPLEMENTATION 
OF THE 
TODD-COXETER ALGORITHM 



Richard J. Bonneau 



December 1973 



This research was supported in part 
by the Raytheon Advanced Degree Program 
and by the Advanced Research Projects 
Agency of the Department of Defense 
under ARPA Order No. 2095 which was 
monitored by ONR Contract No. N00014- 
70-A-0362-0006. 



MASSACHUSETTS INSTITUTE OF TECHNOLOGY 
PROJECT MAC 



CAMBRIDGE MASSACHUSETTS 02139 



An Interactive Implementation 
of the 
Todci-Coxeter Algorithm 



Abstract 

The Todd-Coxeter algorithm provides a systematic approach 
to the enumeration of cosets of a finitely presented group. 
This memo describes an interactive implementation of algorithm, 
including a manual on its use, examples, and methods of 
accessing the program. Applications of this algorithm are 
also discussed. 



TABLE OF CONTENTS 

1 . Introduction 3 

2. User's Manual for the Todd-Coxeter Algorithm 4 

3. Sample Session Number 1 8 

4 . Disk Files for Input and/or Output 10 

5 . Sample Session Number 2 11 

6. Sample Session Number 3 17 

7 . Miscellaneous Information 22 

8. Getting onto the MATHLAB Computer 23 

Bibliography 24 



-3- 



1. Introduction 

This memo presents a user's manual for the operation of an interactive 
version of the Todd-Coxeter algorithm for the computation of the index of 
a subgroup with respect, to a given group. The bulk of the FORTRAN program 
was derived from the program written by Cannon, et. al [1], but has been 
re-organized to provide for interactive use. 

The Todd-Coxeter Algorithm, as described in [2], [3] and [4], provides 
an efficient method for determining the order of a finite group which is 
described in terms of generators and relations. The algorithm also can be 
used to compute the index of any subgroup provided the subgroup is presented 
by generators which are words in the generators of the group. 

This algorithm has been used widely by group theorists and mathematicians 
for a number of applications. These applications include construction of a 
presentation of a known group by generators and relations [5], computation 
of part of the Schur multiplier of a small finite Lie group (PSU(3,4)) [5], 
calculating double cosets H x K given the single coset table form of the sub- 
groups H and K [6], and determination of a set of coset representatives for 
a subgroup [6]. The Todd-Coxeter algorithm has been acknowledged as a power- 
ful and necessary tool for any automated group theory project. 

The current program is written in the FORTRAN IV programming language 
and runs under a simulated PDP-10/50 operating system. The actual configura- 
tion is the Project MAC, MATHLAB PDP-10 computer at M.I.T. 

This memo presents instructions, and examples, for the use of this pro- 
gram, along with an annotated listing of the program. Any comments, criticisms 
or suggestions will be graciously accepted and gratefully acknowledged and 
should be addressed to the author. 

The implementation of the Todd-Coxeter algorithm represents the first 
step in an effort to develop a sophisticated collection of programs to aid 
in computations with groups. It is our hope to be releasing future memos 
detailing improvements and additions to this project. 



-4- 



2. USER'S MANUAL FOR THE TODD-COXETER ALGORITHM 

1. Find a free console on the MATHLAB system. 

Type p ! control-Z n 1 (ctrl-Z), ( Non - Printing ) 



2. The system will type several lines relating to 

the number of users, operating system version, 
and other information. When it has been printed 
out, type 

j: LOGIN GROUP ~| followed by a carriage return (CR). 

3. TEN50 will be awaiting commands when it types a 

new line with only a period on it (.) . 

4. To run the Todd-Coxter program type: 

| R TC (CR)j 

5. At this point, the user has a number of options relating 

to the input to the program: input may either 
be interactive via the teieypeor automatic via 
files on the disk, Similary, the output can be 
printed either on the teleype or onto a file on 
disk- The remainder of the description will assume 
teletype (TTY) for both input and output, 

6. The program now prints out the following question: 

INPUT ON DSK (20) OR TTY (05) ? 

7. Since we desire TTY as input source, we type 

[05 rcRjl 

8. The question is now printed: 

OUTPUT TO DSK (21) OR TTY (05) ? 

9. Again, for TTY output we type 



J05 (CR] 

10. The program now types out the following message: 

TODD-COXETER ALGORITHM running on file: TTY. DAT 
putting, output on file: TTY. DAT 

11. The program now prints out 

NEW PROBLEM INPUT 



-5- 



12. At this point, the program is expecting a control 
number to direct its actions. To begin a new 
problem (i.e., a group and a subgroup), type 



13. 



14. 



TcrTI 



The program will now respond: 

PROBLEM n 
GROUP RELATORS 

where n is the current problem number* 

At this point, the group relators are input, using 
the following scheme: 

For each relator, one line of numbers is input. 
Each relator is numerically represented by a 

sequence of two digit numbers in the form: 

e.x x x (CR) 

112 n 



15. 



where e. is a positive two digit number signifying 
the multiplicity of the relator 
x. is non-zero integer representing either a 
generator of the group (x. positive) or 
the inverse of a generator of the group 
(x. negative) . 

E.g. , if a relator is 

«1 -2 3 

(aba b ) = 1 

then it is entered as the following string: 

030102-1-2-2 (CR) 

After each line is entered the program will verify the 
input by printing (as in the example above) a 



EXP 3 



1 2 -1 -2 -2 



16. Enter as many lines as there are group relators. To 

inform the program that all the relators have been 
input, enter 



r-2 (CR)1 



■6- 



17, The following line will now be typed: 

SUBGROUP GENERATORS 

18- You now enter, in the same format as described above, 
the generators of the desired subgroup; again, 
one line of input per generator, 

19. All the generators have been input, enter a 

This will inform the program that all the input information 
has been given, and also that program execution should 
start. (Note: if the identity subgroup is the desired input 
you need only type -3 when subgroup generators are asked 
for). 

20. The Todd-Coxeter algorithm is now being applied to the 

input data. The program will now terminate in one 
of two ways: 

Successful Termination : In this case, the index 
has been determined and the following is 
printed: 

I NDEX= i MAX= m TO TAT> t 

Here, i will be the index, m will denote 
the maximum number of cosets existing at any 
one time during the execution, and t is the 
total number of cosets created. 

Unsuccessful Termination : In this case, the core 
storage was not sufficient to accomodate the 
computation necessary to complete the problem. 

L00KAHEAD UNABLE TO CONTINUE 

21. In both cases, the program again types out 

NEW PROBLEM INPUT 

22. At this point, the user may wish to proceed in one of 

four ways: 

1) Input a new problem: enter }j-I (cr)j and proceed 

to step 13. 



2) Terminate the session: enter 1-9 (CR)J and proceed to 

step 2: 



3) Maintain the same group as j ust previously input 

but input a new subgroup :^' enter -4 (CRn 
and proceed to step 17, 

4) Maintain the session, W_ ™ th new I/O configuration: 

enter _ [~-8 (CR)| 

and proceed to step §» 

23. At the end of the session, the system types out certain 
run- time statistics, then types 



24. 



EXIT 

tc 

To log off t he system, type j|7cntrl-Z)l and then 
r?T 5gou"t I (CR) 



3 . Sample Session Number 1 
U 

10556) .SLEEP 17, SOu 

ET.'T'rS 811 CONSOLE 7 FREE. 16:46:22 



EL ITS. 811. DDT. 51 6- 
11. USEES 



■ETERIEEDTAL SYSTEE WITH DYRAEOD MAGTAPE RCUTIGRS,ETC 

LED CAUTION, ANP DOET RELOAD OLD SYSTEM V.TTROUT E^EIi^G k,:,. —rr 
Po-Pn rrouv, 

j. i> i. j. 
*:TEE50 



E.PUT Or. DSK (20) 01: TTY (05) 



OUTIUT TO DSK (21) OR TTY (05) ? 

TODD-COXETER ALGORITHM EUEKIEG OR RILE: TTY .DAT 
PUTTING OUTPUT OR PILE: TTY .DAT 



IRE-; PEOPLED IRPIT' 
-1 

-'■•'-n-T T v ' i 



GROUP RELATORS a 

9 1 OL =. H 



<XP 9 



*» 



8 2 

1 2-1-2 A.bflL J b"'c I 



EXP 1 
-2 



-1 -2 



SUBGROUP GEXEEATOR 



JELEX= 



'('/ 



h;-,X= 



\2: 



T01AL= AW 



NEE PEOELEX II3PUT 
_c 



EXECUTION TIME: 4.06 SEC. 

TOTAL ELAPSED TIRE: ., #,_-,^ ^-' C ' 

TO EXECUIICE EXPOSE ii^:i'A,iii. 

EXIT 



-10- 



4. Disk Files for Input and /or Output 

The current implementation of the Todd-Coxeter algorithm 
provides a number of input-output media. In particular, the 
teletype (TTY) has been used for both input and output in the 
sample session. This section will be concerned with the use 
of disk files for both input and output. 

Naming Conventions 

Disk files used for the FORTRAN I/O must agree with the 
following rules: 

1) Each file name is of the form 

Name- ex t 

2) Name must be a 5 character word 

3) Ext must be the 3 characters DAT 

4) For standard (i.e. default) names are: 

INPUT: F0R2O.DAT 
OUTPUT: F0R21.DAT 

The user is permitted to use standard file names or provide 
specific I/O file names. 

Disk Files for Input 

The structure of these files mirror exactly the inputs 
as given in the algorithm. 

A sample session with disk input from file NEWCN. DAT and 
output to TTY is given below, along with listing of 
NEWCN. DAT. 



-11- 



5 . Sample Session Number 2 



EMUI 01; DSK (20) OR TTY (05) ? 

20 

GTAKDAED FILE BAKE (20) OR LOT (22) ? 
22 

ALTER 5 LETTER JTLE NAME 
BE WCA\ AXE 



OUII-UT 10 DSK (21) OR TTY (05) ? 
05 



T0BB-C0XETER ALGORITHM KUNNIIJG OR TILE: KERUERDA: 
TUTTIRG OUTPUT OR PILE: TTY .DAT 

**-x-* ************************** 

PROBLEM 2 



GROUP RELATORS 



JL.Ai."' 


8 


1 




iE-Ax' 


7 


2 




F;XP 


2 


i 


2 


E,aE 


./ 


_-i 


O 



ou I'O itOUiv Or.:i:r.iLHj. Oiuj 



EXP 2 



EXT 1 -12 

INDEX= 448 MAX= 2176 T0TAL= 
****************************** 



■12- 



PROBLEM 3 

GROUP RELATORS 



EXP 


4 




3 




EXP 


5 




2 




EXP 


1 




2 


2 - 


EXP 


2 




2 


3 


EXP 


1 




1 


1 


EXP 


3 




1 


2 


EXP 


11 




1 




EXP 
SUBC 


ROUP 


1 
OEKEE/ 


1 

\TGRS 



1 1-2-1 



I 1 j> 3 



EXP 1 1 

OVERFLOW MAX= 2740 TOTAL= 3U95 

720 COSETS REMAIN AFTER LOOKAKEAD 

INDF:X= 720 MAX= 2740 TOTAL= 35S5 

PROPLEH 4 



GROUP RELATORS 



EXP 


3 


1 




EXP 


2 


1 


2 


EXP 


2 


2 


■z 

-> 


EXP 


2 


3 


1 


EXP 


2 


1 


2 


EX? 


7 


2 




EXP 13 
SUBGROUP 


3 
GENERA 


TO 



?s 



•13- 



oveeflow max= 2744 tctat- 3710 
20c5 cosets remain after lookahead 

ovfmflow max= 2744 total- 4477 
25^7 cosets remain after lookahead 

overflow kax= 2744 iotal=- 4704 
2675 cosets remah: aftfe lookahead 

overflow max= 2744 total- 4776 
10^2 cosets rei-ain after lookahead 

irdrx= 1092 max= 2744 tctat- 4776 

PEOPLES 5 



GROUP REJATORS 



EXP 


3 


EXP 


•^ 
> 


EXP 


3 


EXP 


3 






O v, 



EXP 4 1 3 
1 -3 



-;-■■■ vn 


4 


EXP 


4 


f.;xf 


1 


EXP 


5 



-2 3 

1-2 1 2-3 1 3 1 -3 
1 2 



EXP 5 -1 2 

SUBGROUP GENERATORS 



EXP 1 



EXP 1 



OVERFLOW HAX= 2739 TOTAL- 3394 
2287 COSETS REMAIN AFTER LOOKAHEAD 

OVERFLOW MAX= 2739 TOTAL= 3S : 48 
2539 COSETS REMAIN AFTER LOOKAHEAD 



■14- 



OVERFLOW MAX= 2739 TOTAIj= 4052 
2702 COSETS REMAIN AFTER LOOK AHEAD 

OVERFLOW MAX= 2739 TOTAL= 4089 
2726 COSETS REKAIN AFTER LCOKAHEAD 

OVFRFIOU MAX= 2739 TOTAL= 4102 
2722 COSETS REKAITi AFTER LCOKAHEAD 

OVEEFIOlv HAX= 2739 TOTAL= 41 1S 

2738 COSETS REIAIK AFTER LCOKAHEAD 

OVERFLOW MAX= 2739 TOTAL= 4120 

2739 COSETS EEEAIN AFTER LGOKAIFAD 



LCOKAHEAD UNABLE TO CONTINUE 



■15- 



■ Tnj: 2E7C2.LA2 
-1 

r ■ 
O I 

7 2 
2 1 2 

7-1 2 

2 1 
1-1 2 



-1 



3 - 



■A -l -^ -' "1 -A 



11 






1 1 



rf-:: t t_ 



7 2 



y <- 



c _j 



4 i-o 
7-1 7 



1 7 1- 



1 

1 

: 8 



■16- 



Disk Files for Output 

The structure of these files mirrors exactly the output 
as would be obtained using the TTY for output. In this made, 
however, summary information is output to the TTY. A sample 
session with input from file NEW CN.DAT and output to file 
OUTCN.DAT is given below, as well as the type - out of 
OUT CN.DAT. 



•17- 



6. Sample Session Number 3 



4237) .10! 1,16 $$u 

ML ITS 811 CONSOLE 7 FREE. 17:01:31 

ML ITS. 811. DDT. 51 6. 

12. USERS 

THE 110 BAUD NUMBER IS 258-7894. SORRY ABOUT THE MIX UP 



— PJ 



tlo/rin group 

INIT 
*:TEN 
.R TC 



INPUT Oli DSK (20) OR TTY (05) ? 

2CJ, 

STANDARD FILE NAME (20) OR NOT (22) ? 
22 

ENTER 5 LETTER 1ILE NAME 
liEWCN 

OUTPUT TO DSK (21) OR TTY (05) ? 

STANDARD PILE NAME (21) OR NOT (23) ? 
23 



ENTER 5 LETTER FILE NAME 
OUTCN 



TODD-COXETER ALGORITHM RUNNING ON FILE: NEWCN.DAT 
PUITING OUTPUT 1 ON FILE: OUTCN.DAT 

****■*-************************* 

PROBLEM 1 



INDEX= 448 MAX= 2176 

****************************** 

PROBLEM 2 



TOTAI- 2626 



INDEX= 720 MAX= 2740 
****************************** 

PROBLEM 3 



TOTAL= 3995 



INDEX= 1092 MAX= 2744 
**************** ************** 



TOTAL= 4776 



■18- 



PROBLEM 4 



LOOKAHEAD UNABLE TO CONTINUE 
IliPUT OK DSK (20) OR TTY (05) ? 



TY OUTCN.DAT 



***.************ *************** 

pROBBEi; 1 



GROUP RELATORS 



EXP 


C 


1 




EXP 


7 


2 




EXP 


2 


1 


2 



EXP 3 -1 2 

SUBGROUP GENERATORS 



EXP 2 



1 



-1 2 



INDEX= 448 KAX= 2176 

*^*************************** 

PROBLEM 2 



TOTAL= 2626 



GROUP RELATORS 



EXP 


4 














EXP 


5 


2 












EXP 


1 


2 


2 


-3 


-2 


3 




EXP 


2 


2 


3 


3 








EXP 


1 


1 


1 


1 


1 


-2 -1 


2 


EXP 


3 


1 


2 


3 








EXP 


11 


1 













■19- 



SEHPR05P GENERATORS 1 1 3 



EXP 1 1 

OVERFLOW MAX= 2740 TOTAL= 3995 

720 COSETS REMAIN AFTER LOOK AHEAD 

INDEX= 720 MAX= 2740 TOTAI- 3995 

PROBLEM 3 



GROUP RELATORS 



VYT 


3 


1 




LVP 


2 


1 


2 


EXP 


2 


2 


"a 

> 


EXF 


2 


3 


1 


EXP 


2 


1 


2 3 


EXP 


7 


2 




EXF 13 
SUBGROUP 


3 

GENERATORS 



OVERFLOW MAX= 2744 TOTAL= 3710 

2065 COSETS REMAIN AFTER LOOKAHEAD 



OVERFLOW MAX= 2744 TOTAL= 4477 

2527 COSETS REMAIN AFTER LOQKAHEAD 

OVERFLOW RAX= 2744 TOTAL= 4704 

2675 COSETS REMAIN AFTER LOOKAHEAD 

OVERFLOW MAX= 2744 TOTAL= 4776 

1092 COSETS REMAIN AFTER LOOKAHEAD 

INBEX= 1092 MAX= 2744 TOTAL= 4776 

it***-*********-***************** 



-20- 



PRGBLEK 4 
GROUP IJiLATORS 



AjI-Aj i i"w' : - i' W-* -'< i';l'-i !: ^ 



w V i J -X- .: a.,'W 



-2L 



>2 CCi.ll 



;.'T r < 



ALCA' 



a?-;aa; afte;: 



.A. 



\V_ AT 



20 



T.U.r.Aii-^AD Li-jAi-.J.. 



1 .!. J 'i o.l: 



-22- 



7. MISCELLANEOUS INFORMATION 
Typing Errors 

1. Before carriage return 

2. Use "RUBOUT" or "DELETE" Keys 

3. Will echo the deleted character 

4. May be used in succession to delete several char. 
Program Interrupt : 

1. Type control -C (f c) once 

2. Until EXIT 

ft 

appears 
To continue after t C interrupt : 

1. Type CONT 

2. Back to same spot! 
To Restart 

1. Type START at monitor level 

2. Continue as normal 

Current Limitations 

1. Number of generators ^ 9. 

2. Number of terms in generators or relation words ^ 40, 



-23- 



8. Getting onto the MATHLAB Computer 

In order to run the Todd-Coxeter Algorithm on a given problem, one must 
first gain access to the MATHLAB computer located at M.I.T. There are three 
ways of doing so: 

1) If you are at M.I.T. and have access to a free ML console, 
simply follow the instructions in Section 2 of this memo. 

2) If you are not at M.I.T., but have access to a computer on 
the ARPA network of computers, then you can ur 2 the MATHLAB 
computer by accessing it over the network. Consult your 
local expert on the ARPA network to find out how to do this. 

3) You can access the MATHLAB computer using a terminal (teletype 
or Memorex) by telephone, If you have an acoustic coupler or 

a Dataphone. The telephone numbers are: available from Dr. 
Vera Pless or Richard Bonnea^, telephone number (617) 253-6026. 



-24- 



BIBLIOGRAPHY 

[1] Gannon, et al., "Implementation and Analysis of the Todd-Coxeter Al- 
gorithm", to appear in Math. Comp . 

[2] Coxeter & Todd, "A Practical Method for Enumerating Gosets of a Finite 
Abstract Group", Proc. Edinburgh Math. Soc , (2), 5(1936), 26-74. 

[3] J. Leech, "Coset Enumeration on Digital Computations", Proc Comb. Phil. 
Soc , 59(1963), 257-267. 

[4] H. Trotter, "A Machine Program for Coset Enumeration", Canadian Math. Bull. 
Vol. 7, No. 3, July 1964, pp. 357-368. 

[5] Grover, et al . , "Applications of Coset Enumeration", 2nd Symposium on 
Symbolic and Algebraic Manipulation , ACM, March 1971, pp. 183-187. 

[6] J. Cannon and G. Hovas , "Applications of the Todd-Coxeter Algorithm", 
Technical Report No. 9, Computer Aided Mathematics Project, Department 
of Pure Mathematics, University of Sydney, Sydney, Australia, June 1973. 



MIT/LCS/TM-35 



AN INTERACTIVE IMPLEMENTATION 

OFTHE 
TODD-COXETER ALGORITHM 



Richard J. Bonneau 



December 1973 



MASSACHUSETTS INSTITUTE OF TECHNOLOGY 
PROJECT MAC 



Reply to: Projecf MAC 

545 Technology Square 
Cambridge, Mass. 02139 

Telephone: 3 ~5 856 



PUBLICATIONS TR/TM FORM 



TITLE OF THESIS OR REPORT: An Interactive Implementation of 

the Todd-Coxeter Algorithm 



AUTHOR(S) Richard J. Bonneau 



NO. ASSIGNED: MAC TM-35 

Do you recommend it be made into a Project MAC technical 
report? If so, what type? 



Technical Report (formal, widely distributed) 

_x Technical Memo (informal, limited distribution) 

Do not print as a MAC publication 



i i 

i ■ f 




? /// \ — . ? ? 

(/ .* A: r j 




Signature of M^C Group Leader 




^ *^3r 5 , 1 °t 7 X 





Date 



PUBLICATIONS DISTRIBUTION 

PROJECT MAC, ROOM 417-A 

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 

545 TECHNOLOGY SQUARE 

CAMBRIDGE, MASS. 0213 9 



December 1973 



We have recently issued Project MAC Technical Memorandum TM-35: 

An Interactive Implementation of the 
Todd-Coxeter Algorithm 

Richard J. Bonneau 
AD 770-565 



ABSTRACT 

The Todd-Coxeter Algorithm provides a systematic approach 
to the enumeration of cosets of a finitely presented group. 
This memo describes an interactive implementation of algorithm, 
including a manual on its use, examples, and methods of 
accessing the program. Applications of this algorithm are also 
discussed.